#pragma once

#include "iostream"
#include "vector"
#include "stack"
#include "unordered_map"
#include  "queue"
#include "TypeDefin.h"

using namespace std;
/*
 * 来看一下几篇面经的原文叙述else
}
 l2->next= merge(l1,l2->next)

链表，奇数位置按序增长，偶数位置按序递减，如何能实现链表从小到大？（2020.10 字节跳动-后端）[2]
奇偶生序倒序链表的重新排序组合，例如：18365472（2020.08 字节跳动-后端）[3]
1->4->3->2->5 给定一个链表奇数部分递增，偶数部分递减，要求在O(n)时间复杂度内将链表变成递增，5分钟左右（2020.07 字节跳动-测试开发）[4]
奇数位升序偶数位降序的链表要求时间O(n)空间O(1)的排序？(2020.07 字节跳动-后端)[5]
可见，无论是后端还是测试开发，都曾被考察过这道题，而且这道题并非力扣上的题目，大家一定要注意！！

题目描述

给定一个奇数位升序，偶数位降序的链表，将其重新排序。

输入: 1->8->3->6->5->4->7->2->NULL
输出: 1->2->3->4->5->6->7->8->NULL
题目分析



1. 按奇偶位置拆分链表，得1->3->5->7->NULL和8->6->4->2->NULL
2. 反转偶链表，得1->3->5->7->NULL和2->4->6->8->NULL
3. 合并两个有序链表，得1->2->3->4->5->6->7->8->NULL
 * */

//我他妈的哭了草做了估计得20分钟了
ListNode *reverseNode(ListNode *&list) {
    if (list == nullptr || list->next == nullptr)
        return list;

    auto ret = reverseNode(list->next);

    list->next->next = list;
    list->next = nullptr;
    return ret;

}

ListNode *merge(ListNode *l1, ListNode *l2) {
    if (!l1)
        return l2;

    if (!l2)
        return l1;

    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
    } else {
        l2->next = merge(l1, l2->next);
    }


    return l1->val < l2->val ? l1 : l2;
}


//1->8->3->6->5->4->7->2->NULL
static void merageList(ListNode *&list) {
    //分割奇数偶数list
    int count = 0;
    ListNode *jishu = nullptr;
    ListNode *oushu = nullptr;

    ListNode *jishuHead = nullptr;
    ListNode *oushuHead = nullptr;
    while (list) {
        auto tnext = list->next;
        if ((list->val) % 2 != 0) {
            if (!jishu) {
                jishu = list;
                jishuHead = jishu;
            } else {
                jishu->next = list;
                jishu = list;
            }
        } else {
            if (!oushu) {
                oushu = list;
                oushuHead = list;
            } else {
                oushu->next = list;
                oushu = list;
            }

        }
        list->next = nullptr; //这边有坑 这个得赋值为null
        // count++;
        list = tnext;

    }

    auto l1 = reverseNode(oushuHead);


    //合并两个list  1 2
//    auto dummpy=new ListNode(0);
//    dummpy->next= nullptr;
//    auto dummpyd=dummpy;
//    while (l1&&jishuHead)
//    {
//        if (l1->val<jishuHead->val)
//        {
//             auto t=l1->next;
//             l1->next=dummpy->next;
//             dummpy->next=l1;
//             dummpy=l1;
//             l1=t;
//        }else{
//            auto  t=jishuHead->next;
//            jishuHead->next=dummpy->next;
//            dummpy->next=jishuHead;
//            dummpy=jishuHead;
//            jishuHead= t;
//        }
//
//    }
//
//    while (l1)
//    {
//        auto t=l1->next;
//        dummpy->next=l1;
//        dummpy=l1;
//        l1=t;
//    }
//
//    while (jishuHead)
//    {
//        auto  t=jishuHead->next;
//        dummpy->next=jishuHead;
//        dummpy=jishuHead;
//        jishuHead= t;
//    }

    auto dummpyd = merge(jishuHead, l1);
    while (dummpyd) {
        cout << dummpyd->val << " ";
        dummpyd = dummpyd->next;
    }

    /*
     *     auto  l1=new ListNode(1);
    auto  l2=new ListNode(8);
    auto  l3=new ListNode(3);
    auto  l4=new ListNode(6);
    auto  l5=new ListNode(5);
    auto  l6=new ListNode(4);
    auto  l7=new ListNode(7);
    auto  l8=new ListNode(2);
   // auto  l1=new ListNode(1);
   l1->next=l2;
   l2->next=l3;
   l3->next=l4;
   l4->next=l5;
   l5->next=l6;
   l6->next=l7;
   l7->next=l8;
   l8->next= nullptr;
     *
     *
     *
     * */

}
